from typing import List


class Solution:
    """
    方法：回溯算法
    Args:
        nums: List[int] - 输入的整数数组
    Returns:
        List[List[int]] - 所有可能的子集
    Time: O(n * 2^n) - 共有2^n个子集，每个子集需要O(n)时间复制
    Space: O(n) - 递归栈深度为n，path数组长度为n
    """

    def subsets(self, nums: List[int]) -> List[List[int]]:
        ans = []
        path = []
        n = len(nums)
        def backtrack(i: int) -> None:
            ans.append(path.copy())
            for j in range(i, n):# 枚举选择的数字
                path.append(nums[j])
                backtrack(j+1)
                path.pop()
        backtrack(0)
        return ans

    def subsets1(self, nums: List[int]) -> List[List[int]]:
        ans = []
        path = []
        n = len(nums)
        def backtrack(i: int) -> None:
            if i == n:  # 子集构造完毕
                ans.append(path.copy())  # 复制 path，也可以写 path[:]
                return
                
            # 不选 nums[i]
            backtrack(i + 1)
            
            # 选 nums[i]
            path.append(nums[i])
            backtrack(i + 1)
            path.pop()  # 恢复现场
        backtrack(0)
        return ans